package _06_动态规划;

public class _45_跳跃游戏II {


    public static void main(String[] args) {

        _45_跳跃游戏II v = new _45_跳跃游戏II();

        int[] ins = {2, 3, 1};
        System.out.println(v.jump(ins));

    }

    public int jump(int[] nums) {
        int end = 0;
        int maxLen = 0;
        int step = 0;
        int len = nums.length - 1;
        for (int i = 0; i < len; i++) {
            maxLen = Math.max(maxLen, i + nums[i]);
            if (i == end) {
                end = maxLen;
                step++;
            }
        }
        return step;
    }

    // 反向贪心查找
    public int jump1(int[] nums) {
        // 从左往右找到第一个可以到达结束位置, 并且更改结束位置的位置
        int step = 0;
        int end = nums.length - 1;
        while (end > 0) {
            for (int i = 0; i < end; i++) {
                if (i + nums[i] >= end) {
                    end = i;
                    step++;
                    break;
                }
            }
        }
        return step;
    }

}
